留言設定

Memory Allocation

tags: sysprog

討論區連結

主講人: jserv / 課程討論區: 2016 年系統軟體課程
:mega: 返回「嵌入式作業系統設計與實作」課程進度表

動態記憶體分配對Realtime System的影響

Glibc malloc()分配記憶體的方式

  1. 分配heap上面的空間(使用brk()sbrk()) => small allocations
  2. 分配anonymous memory(使用mmap()) => large allocations

membroker

System-wide Memory Management for Linux Embedded Systems

What is anonymous memory?

brk() is bad for other realtime threads

down_write(current->mm->**mmap_sem**) 會造成indefinite waiting

Glibc cannot shrink heap until highest allocated object is freed

VMA

常用的動態記憶體分配演算法

TLSF(Two Level Segregated Fit)

The first-level array divides free blocks in classes that are a power of two apart (16, 32, 64, 128, etc.); and the second-level sub-divides each first-level class linearly.

TLSF特性的比較

dlmalloc / ptmalloc2

scalloc

Understanding glibc malloc (ptmalloc2)

Memory request size

arena and thread

arena即為malloc從系統取得的連續記憶體區域,分為main arena與thread arena兩種。

每個thread在呼叫malloc()時會分配到一個arena,在開始時thread與arena是一對一的(per-thread arena),但arena的總數有限制,超過時threads會開始共用arena:

此設計是為了減少多threads記憶體浪費,但也因此glibc malloc不是lockless allocator,對於有許多threads的server端程式來說,很有可能影響效能

www.google.com.tw/?gws_rd=ssl

Heap data structures

Main arena vs Thread arena :

multiple heap Thread arena :

Chunks

Allocated chunk :

_Free Chunk _:

Bins

bins是紀錄free chunks的資料結構(freelist),依據其大小和特性分成4種 :

(以下的數值為32bit系統,64bit *2)

_Fast Bin _:

_Unsorted Bin _:

_Small Bin _:

_Large Bin _:

Top chunk

在arena邊界的chunk,若所有bin皆無法allocate則由這裡取得,若仍不夠則用brk / mmap延展

Last Remainder Chunk

最近一次分割的large chunk,被用來滿足small request所剩下的部分

malloc流程

free流程

簡單測試 : malloc(40 * sizeof(int));

Introduction to Scalloc

簡介

scalloc的設計強調在concurrent環境下的表現,尤其是在thread / core增加時的performance (secaling),並且保持一定的記憶體效率。其設計仰賴64-bit的記憶體空間與linux demand paging的特性,包含了 :

Real Spans & Virtual Spans

span是allocator用來分配記憶體的概念單位,scalloc使用雙層(real & virtual) span作為分割記憶體的單位。記憶體區段(arena)先分割成virtual span,其內再分成real span,於real span內進行allocation。

Real span & size class

每個real span內依size class被分為相同大小的blocks,real span有29種size class,但real span本身只有9種大小。size class 1-16分別為16bytes至256bytes,每個class相差16bytes(與tcmalloc相同),它們的real span皆有相同的size;17-29分別為512bytes至2MB,每個class相差2倍。>1MB的allocation則直接以mmap處理。

Virtual span

在scalloc初始化時,會進行一次32TB的mmap,此區段稱為arena,其空間被分成以2MB size , 2MB aligned的區塊,即為virtual span。每個使用中的virtual span包含一個real span,virtual span的size class即為該real span的size class,通常real span的size會比virtual span小許多。virtual span有以下特性 :

當virtual span清空後,會放入free list(即span pool),為限制physical fragmentation,若real span大於一定大小,會以madvise釋放空間。

span-pool是一個global資料結構,由stack-like pools的array組成,array以size class為單位。stack-like pools在單thread情形下即為stack。

size class的分割以pre-allocated array的index達成,每個entry內又有一個pre-allocated array(pool array),其entry內含lock-free的Treiber stack,index則為執行時的core number。Treiber stack由元素的singly linked list組成,push與pop以對top pointer的atomic compare-and-swap實作。為避免ABA問題,實作中使用包含在top pointer中的16-bit ABA counter。

以下是Span-pool的pseudo code :

put

thread會先取得real-span index與core index並放入對應的pool : 在放入之前,若其real-span size > MADVISE_THRESHOLD,則用madvise釋放記憶體。MADVISE_THRESHOLD預設為32KB,即size class增加方式的分界(512bytes)的real-span size。

get

先試由所屬real-span / core index取得span(fast path);若失敗,則搜尋整個pool,試取得空span;若仍失敗,由arena取得新的virtual span。

Frontend: Allocation and Deallocation

span可以有幾種不同的狀態 :

span可以是以下其中之一 : expected, free, hot, floating, reusable。

其他3種狀態皆在frontend,且span此時有所屬的span size

每個span在frontend時,都會被分配到一個local-allocation buffer (LAB),LAB可以調整為thread-local(TLAB)或core-local(CLAB)模式,分別由每thread / core擁有一個。 LAB內包含每size class一個的hot span,與一些也以size class分類的reusable span。

span內的free若是其他thread進行的稱為remote free,自身thread進行的為local free。malloc皆是由local hot span進行。針對remote free的fragmentation問題,scalloc使用兩個free list將local與remote free分開處理。

Allocation

Deallocation

Operation Complexity

allocation

只考慮hot span且不進行任何cleanup,在沒有contention的情形下 :

有contention情形下,因同步進行的deallocation,可能需要考慮1個以上的reusable span,但至少有1個thread可以以constant-time執行

deallocation

只考慮block所在的span :

Span-pool

為constant-time modulo synchronization (span-pool整體為lock-free)

Implementation Details

Real Span

Auxiliary structures and methods

Frontend

Thread Termination

由於LAB沒有對所有span的reference (例如floating span),要找出orphaned,必須比較span的owner與LAB的owner,兩者不同或owner==TERMINATED皆是orphaned span。orphaned皆為floating,於deallocate時由新的LAB adopt。

Handling Large Objects

大於1M直接使用mmap。

Scalloc design decisions

fragmentation testing

主要策略

測量最大可用的block(freemax)相對於所有可用空間(free)的比率,freemax相對越小就表示連續的的block越小,即fragmentation 變大。

allocated相對於總記憶體使用的比率,剩下的空間即是浪費掉的空間,可能的來源有overhead、fragmentation等。

fragmentation 可能造成新的allocation無法使用已經free的記憶體,造成總使用空間增加,utilization下降。 若一個process的memory utilization因為fragmentation持續降低,最後可能因為使用空間太大而OOM。

實例 (paper)

更清楚的解釋上述四種數值化模式 https://paper.dropbox.com/doc/Fragmentation-4v9zRLIanLfNw1BoiZ0VH

實驗考量

(可能的)測量方法

Memory allocator研究 - jemalloc

設計上重視cache locality勝於減少working set pages使用數目,減少記憶體的使用量可以達到此目的;因為temporal locality通常也意味著spatial locality,所以也儘可能分配連續的記憶體

(同樣地)提到false cache sharing對效能的衝擊

實驗重現與驗證

**ROBUST MEMORY MANAGEMENT USING REAL TIME CONCEPTS **

Understanding glibc malloc

實驗設計

https://github.com/jacky6016/malloc-benchmark

實驗測量方向



Buddy System

source ]

Buddy System 是種記憶體配置 (memory allocator) 演算法,先將記憶體分成很多size,最小的單位即是一個 page,這個方式會減少 external fragmentation,因為這個機制就是典型的你有多大就放再那一個適合大小櫃子裡,再來還是會有internal fragmentation 的問題,因位我們已經把一個基本單位規定成一個 Page ,而假如一個 Page 是 64K,那麼假如只要儲存一個52K的東西,那麼就會有12K是空的,這個的好處就是可以分的很清楚,哪個page是誰的,就我認知,解決external fragment會是比較好的選擇,因位假如發生的話單位都是以page來算,internal 可能是用byte來算的。

實例解釋:

現在我們有4個東西要儲存 A , B , C , D, 首先我們第一個要儲存的是 A,而A是佔了 64KB的空間(也可能是基本單位 page size),所以我們開始作對折的動作,step 1 開始,step 2.1 開始做第一次對折,發現空間還是大於他很多,所以我又再切step 2.2,一直切到step 2.5 才終於剛剛好放下,再來是放 B ,他佔了 264KB,然後我發現我剛好有對的地方所以直接放下去step 3 ,再來換C,而C的流程跟B一樣,就是D了,他佔了 264KB,但觀察step 4和‵step 5.1 其實是沒有剛好放的下D的空間,所以他又再切它,最後這些A B C D 總有用完的時候,就可以將他回收成原本的memory樣式 step 9.1開始。

Benchmarking

Scalloc-artifact test suite測試數據

MADVISE

重現 note-about-madvise 部落格文章上,測試madvise的程式碼。並且在進行修改之後,開了一個新專案放到github上面,照著README操作就可以重現該篇文章上使用madvise帶來效能上的改進。

https://github.com/enginec/madviseBench

分析Memory Usage Pattern製作benchmark

目前我的想法是透過分析一個程式的memory usage pattern,例如可能是頻繁的小區塊分配與釋放、或是每次索取的記憶體大小差異g很大等,產生對應的benchmark,之後就可以利用這個benchmark來比較不同memory allocator的效能差異。

原本的想法是參考malloc_count,透過動態連結malloc到測試程式,得知每次malloc呼叫大小和順序,並用這個資料去產生benchmark。

但這種作法的盲點在,假設我們要分析的程式是multi-threaded,那麼光是紀錄每次呼叫malloc的大小和順序是不夠的。我們必須要能夠模擬出每個thread使用malloc/free的大小和時間點,用於建立對應的benchmark,再拿這個benchmark去測試各種malloc實作才有意義。因為有些malloc實作支援multithread,要這樣做才能真正測出各種malloc實作的差異。

目前下幾個關鍵字搜尋,找到兩個商用軟體好像能分析thread等級的memory usage情況。

intersec 記憶體系列文章

Reference

Implementations & Tools

Implementations

Benchmarks

Tools

全部展開回到頂部移至底部
Max height: 25 of 26
Hide Download Bar
Ctrl + Shift + Z = Show/Hide Download Bar
下載
Download Manager (S3)
清除
按左鍵: 移除全部已完成檔案
按右鍵: 復原上次清除項目
100%
下載歷史記錄
Download list is empty
f60a6c47c1bf892a2c4b76e4bb7c1cf83b58.pdf
100%
--:--
617 KB
-.--
f60a6c47c1bf892a2c4b76e4bb7c1cf83b58.pdf
Source:
從:
儲存至:
C:\Users\redegg\Desktop\f60a6c47c1bf892a2c4b76e4bb7c1cf83b58.pdf
狀態:
617 KB / 617 KB ( -.-- )
檔案大小:
617 KB
Virus scan:
開始時間:
2021.01.25 - 22:50:40
完成時間:
<00:01
剩餘時間:
--:--
完成百分比:
100%
平均速度:
1.26 MB/秒
mouse double click: download pause/resume
mouse middle click: download cancel
mouse double click: open file
mouse double click + Ctrl: open dir
mouse middle click: delete from list
mouse middle click + Ctrl: delete from system
press mouse button + Ctrl: drag & drop
實時系統動態內存算法分析dsa(二)--TLSF代碼分析_螞蟻的專欄-CSDN博客.html
100%
--:--
5.51 MB
-.--
實時系統動態內存算法分析dsa(二)--TLSF代碼分析_螞蟻的專欄-CSDN博客.html
Source:
從:
儲存至:
C:\Users\redegg\Desktop\實時系統動態內存算法分析dsa(二)--TLSF代碼分析_螞蟻的專欄-CSDN博客.html
狀態:
5.51 MB / 5.51 MB ( -.-- )
檔案大小:
5.51 MB
Virus scan:
開始時間:
2021.01.25 - 23:07:12
完成時間:
<00:01
剩餘時間:
--:--
完成百分比:
100%
平均速度:
12.73 MB/秒
mouse double click: download pause/resume
mouse middle click: download cancel
mouse double click: open file
mouse double click + Ctrl: open dir
mouse middle click: delete from list
mouse middle click + Ctrl: delete from system
press mouse button + Ctrl: drag & drop